|
Dijkstra路由最短路径算法
Dijkstra路由最短路径算法算法实现
Dijkstra路由最短路径算法
先简单解释一下该算法的字面含义：根据百度百科的解释为：是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
下面开始图文解释：
我们要寻找从a点到f点的最短路径，上面的数字表示权重，代表每经过一个节点所要付出的代价。  从a点选取一个权重最小的节点c：
然后根据选中的节点进行更新，更新的是从a点到各个节点的权重。  然后更新下一个权重最小的节点b：
去掉的节点表示不会再从那个节点路过，因为有更优秀的节点取代。  接下来选取节点e：  接下来选取d：
该节点选取后就能更新完所有相关的最终节点，确定出最佳路线。 
算法实现
public static final int INF = 99999;
public static final int[][] a = {
{0,300,100,INF,INF,INF}, //顶点a
{300,0,150,50,INF,INF}, //顶点b
{100,150,0,200,200,INF},//顶点c
{INF,50,200,0,600,400},//顶点d
{INF,INF,200,600,0,700},//顶点e
{INF,INF,INF,400,700,0} //顶点f
};
//是否访问过该节点
public static boolean[] b = new boolean[a.length];
//前驱节点 通过该节点可以追踪最佳链路
public static int[] prev = new int[a.length];
//各个节点的最短路径
public static int[] dist = new int[a.length];
public static void solution(){
dist[0] = 0;
b[0] = true;
int tmp;
int k = 0;
//从顶点a到定点f
for (int i = 0; i
int min = INF;
for (int j = 0; j
min = dist[j];
k = j;
}
}
b[k] = true;
// 选中一个节点后 根据这个节点更新所有和它相关的节点
for (int j = 0; j
dist[j] = tmp;
prev[j] = k;
}
}
}
}
也解答了我上一篇文章的一个遗留问题
按下回车的那一刻发生了什么？
更多干货内容请关注公众号：“计算机基础爱好者”
谢谢
|